package com.zhanghp.class035;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 实现LRU结构
 * <p>
 * 测试链接 : https://leetcode.cn/problems/lru-cache/
 * <p>
 * 利用双节点链表实现
 *
 * @author zhanghp
 * @since 2024/4/11 9:57
 */
public class Code02_LRU {

    static class LRUCache {

        public Map<Integer, DoubleNode> lru;

        public final int capacity;

        public DoubleList nodeList;

        public LRUCache(int capacity) {
            this.lru = new HashMap<>();
            this.capacity = capacity;
            this.nodeList = new DoubleList();
        }

        public int get(int key) {
            if (lru.containsKey(key)) {
                DoubleNode node = lru.get(key);
                nodeList.moveNodeToTail(node);
                return node.val;
            }
            return -1;

        }

        public void put(int key, int value) {
            if (lru.containsKey(key)) {
                DoubleNode node = lru.get(key);
                node.val = value;
                nodeList.moveNodeToTail(node);
            } else {
                if (lru.size() == capacity) {
                    lru.remove(nodeList.removeHead().key);
                }
                DoubleNode node = new DoubleNode(key, value);
                lru.put(key, node);
                nodeList.add(node);
            }
        }


        static class DoubleNode {

            /**
             * 用于删除时使用
             */
            public int key;

            public int val;

            public DoubleNode last;

            public DoubleNode next;

            public DoubleNode(int key, int val) {
                this.key = key;
                this.val = val;
                last = next = null;
            }
        }

        // 双向节点链表
        static class DoubleList {
            public DoubleNode head;
            public DoubleNode tail;

            public DoubleList() {
                head = tail = null;
            }

            public void add(DoubleNode node) {
                if (node == null) return;

                if (head == null) {
                    head = tail = node;
                } else {
                    tail.next = node;
                    node.last = tail;
                    tail = node;
                }
            }

            public void moveNodeToTail(DoubleNode node) {
                if (tail == node) return;

                if (head == node) {
                    head = node.next;
                    head.last = null;
                } else {
                    // 头，尾边界都考虑完，node只能在中间
                    // a <=> node <=> c
                    // a <=> c
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                // 尾部处理
                node.last = tail;
                node.next = null;
                tail.next = node;
                tail = node;
            }

            public DoubleNode removeHead() {
                DoubleNode ans = head;
                if (head == tail) {
                    head = tail = null;
                } else {
                    head = ans.next;
                    head.last = null;
                    // 将原先的头结点置空
                    ans.next = null;
                }
                return ans;
            }


        }
    }


}
